A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Certain devices within the network referred to as routers use routing protocols to exchange and accumulate topology information that describes the network. This allows a router to construct its own routing topology map of the network. Upon receiving an incoming data packet, the router examines keying information within the packet and forwards the packet in accordance with the accumulated topology information.
Many routing protocols use flooding-based distribution mechanisms to announce topology information to routers within the network. These routing protocols typically rely on routing algorithms that require each of the routers to have synchronized routing topology information. For example, Open Shortest Path First (OSPF) and Intermediate system to intermediate system (IS-IS) routing protocols are link state protocols that use messages conveying link state representations to ensure their routing topology is synchronized with respect to available interfaces, metrics and other variables associated with network links. For example, OSPF utilizes Link State Advertisements (LSAs) while IS-IS uses Link State Protocol Data Units (PDUs) to exchange information. Messages such as the used to convey link state representations in accordance with a link state protocol are generally referred to herein as link state advertisements (LSAs), and OSFP LSAs and IS-IS LS PDUs are examples of such LSAs.
A router operating in accordance without a link state protocol typically floods link state advertisements throughout the network such that every other router receives the link state advertisements. In network topologies where routers are connected by point-to-point connections, each router floods link state advertisements to adjacent routers reachable on each interface to ensure synchronization. In networks using multi-access media, such as an Ethernet network, the routers within the network flood the link state advertisements to all other routers. In either case, the receiving routers construct and maintain their own network topologies using the information received via the link state advertisements. These link state advertisements may include information identifying a cost metric associated with the link, as well as any other constraints commonly employed for selecting a path through a network in accordance with a link state protocol.
Some types of link state advertisements may be rather large in size as a result of, as one example, having to specify a link metric from the advertising router to each of the other routers in the network. In networks where conditions rapidly change, such as radio, satellite, or any other form of wireless-based networks that may be subject to electronic interference, the routers may generate and send large numbers of link state advertisements advertising the change in condition by updating various link metrics very frequently. The number of link state advertisements in these networks may potentially consume significant network bandwidth while also possibly consuming significant processing resources of the routers when generating, processing and sending/receiving these link state advertisements.